package org.tang.tianchi.notes.array;

/**
 * 给你一个长度为 n 的整数数组 nums 和 一个目标值 target。请你从 nums 中选出三个整数，使它们的和与 target 最接近。
 * 返回这三个数的和。
 * 假定每组输入只存在恰好一个解。
 * <p>
 * 示例 1：
 * <p>
 * 输入：nums = [-1,2,1,-4], target = 1
 * 输出：2
 * 解释：与 target 最接近的和是 2 (-1 + 2 + 1 = 2) 。
 * 示例 2：
 * <p>
 * 输入：nums = [0,0,0], target = 1
 * 输出：0
 * 提示：
 * <p>
 * 3 <= nums.length <= 1000
 * -1000 <= nums[i] <= 1000
 * -104 <= target <= 104
 */

import java.util.Arrays;
import java.util.Random;

/**
 * 题解：
 * 总结:length>3,从nums选取三个数，和最接近target
 * 情况1：length=3,直接为三元素
 * 情况2：length>3,以下内容在情况2下讨论
 * <p>
 * 不建议做减法，使用加法进行计算.
 * <p>
 * 解法1：
 * 暴力求解：求value
 * 逐个获取参数，三个for循环，加法，获取和                 中间值sum
 * temp = target-sum                                中间值temp
 * 如果temp的绝对值小于设置的最小值，将value设置为新的值    设置最小值minValue，初始值MAX_VALUE
 * 循环结束，返回value
 * <p>
 * 解法2：      ->排序，剪除后面的内容,复杂度没有改变
 * 暴力求解，在解法1的基础上做改变：
 * 该题目和下标无关，那么可以进行升序排序
 * 在坐标中，将target视为一个点，数组视为一组升序的坐标点
 * sum = num1 + num2 + num3   和的值称为a1
 * abs(target - sum)          差值的绝对值称为a2
 * 当只有num3在向后移动，a2是一个先小后大的曲线
 * 因为num3在变大，其他两个值不变，和必然变大
 * num3在往后移动，a1始终在变大，如果a1大于a2，说明后续的值始终会大于a2，此时的a2已经是最小值
 * 此时可以跳出第三层循环，num2往后移动，再次循环
 * <p>
 * 解法3：    ->排序，固定一个，小，左进一位；大，右减一位
 * 在解法1上做出改变，排序
 * 三个数：  第一个数遍历nums[:-2],设为a1   第二个数为a1+1  设为a2     第三个数为nums[len(nums)-1] 设为a3
 * 如果abs(target-(a1+a2+a3)) 的值  比 最小值大， a2向右移动；相反，a3像左移动
 * 每次只移动一个数，他们的和逐渐朝着目标值接近；当a3<=a2的时候，a1+1,进入下一个循环
 */


public class 最接近的三数之和 {

    public static void main(String[] args) {
//        int[] nums = getArray(-184,790,10);
        int[] nums = new int[]{-1, 2, 1, -4};
        System.out.println(Arrays.toString(nums));
        int target = 1;
        System.out.println(threeSumClosest06(nums, target));
//        System.out.println(threeSumClosest(nums, target));
    }

    public static int[] getArray(int start, int end, int size) {
        int[] value = new int[size];
        Random rand = new Random();
        for (int i = 0; i < size; i++) {
            value[i] = rand.nextInt(end - start + 1) + start;
        }
        return value;
    }

    /**
     * 给你一个长度为 n 的整数数组 nums 和 一个目标值 target。请你从 nums 中选出三个整数，使它们的和与 target 最接近。
     * 返回这三个数的和。
     * 假定每组输入只存在恰好一个解。
     * <p>
     * 示例 1：
     * <p>
     * 输入：nums = [-1,2,1,-4], target = 1
     * 输出：2
     * 解释：与 target 最接近的和是 2 (-1 + 2 + 1 = 2) 。
     * 示例 2：
     * <p>
     * 输入：nums = [0,0,0], target = 1
     * 输出：0
     * 提示：
     * <p>
     * 3 <= nums.length <= 1000
     * -1000 <= nums[i] <= 1000
     * -104 <= target <= 104
     */
    public static int threeSumClosest(int[] nums, int target) {
        int value = 0;
        int minValue = Integer.MAX_VALUE;
        String s = "";
        for (int x = 0; x < nums.length - 2; x++) {
            for (int y = x + 1; y < nums.length - 1; y++) {
                for (int m = y + 1; m < nums.length; m++) {
                    int sum = nums[x] + nums[y] + nums[m];
                    int temp = target - sum; // 1 - 2 = -1    1 - (-3) = 2    1 - 3 = -2
                    if (Math.abs(temp) < minValue) { // 只有一个答案
                        minValue = Math.abs(temp);
                        value = sum;
                        s = "x:" + nums[x] + " y:" + nums[y] + " m:" + nums[m];
                    }
                }
            }
        }
        System.out.println(s);
        return value;
    }


    public static int threeSumClosest05(int[] nums, int target) {
        Arrays.sort(nums);
        if (nums.length == 3) {
            return nums[0] + nums[1] + nums[2];
        }
        int road = Integer.MAX_VALUE;  // 距离，求最小的距离
        int value = Integer.MAX_VALUE;
        for (int first = 0; first < nums.length - 2; first++) {
            for (int second = first + 1; second < nums.length - 1; second++) {
                for (int third = second + 1; third < nums.length; third++) {
                    int roadDemo = Math.abs(nums[first] + nums[second] + nums[third] - target); // 距离
                    if (road > roadDemo) { // 替换为最小的距离
                        road = roadDemo;
                        // 记录最小的和值
                        value = nums[first] + nums[second] + nums[third];
                    }
                }
            }
        }
        return value;
    }

    // first确定，third从最后一个值减小，second增大，直到和值减去target不大于0,check
    public static int threeSumClosest06(int[] nums, int target) {
        Arrays.sort(nums);
        int road = Integer.MAX_VALUE;
        int value = 0;
        for (int first = 0; first < nums.length - 2; first++) {
            int second = first + 1;
            int third = nums.length - 1;

            while (third > second) {
                int diff = nums[first] + nums[second] + nums[third] - target;
                int roadDemo = Math.abs(diff);
                if (roadDemo < road) {
                    road = roadDemo;
                    value = diff + target;
                }
                if (diff > 0) {
                    third--;
                } else if (diff < 0) {
                    second++;
                } else {
                    return value;
                }
            }

        }
        return value;
    }


    // 该方法未能通过，异常奇怪，未找到原因
    public static int threeSumClosest02(int[] nums, int target) {
        Arrays.sort(nums);
        int value = 0;
        int minValue = Integer.MAX_VALUE;
        for (int x = 0; x < nums.length - 2; x++) {
            for (int y = x + 1; y < nums.length - 1; y++) {
                for (int m = y + 1; m < nums.length; m++) {
                    int sum = nums[x] + nums[y] + nums[m];
                    int temp = target - sum; // 1 - 2 = -1    1 - (-3) = 2    1 - 3 = -2
                    if (Math.abs(temp) < minValue) { // 只有一个答案
                        minValue = Math.abs(temp);
                        value = sum;
                        continue;
                    }
                    break;
                    // 0,3,97,102,200   target=300
                    // 问题，新的值进来，将会出现Bug，比如x = 0 , y = 102, m = 200,  差值t = 2
                    // 下一轮 x = 3, y =97, m = 102    差值为98，直接跳过了后面的200
                    // 如果非要剪枝，只能设置一个临时最小值，等 每一轮循环完毕，再去比较两个最小值。
                }
            }
        }
        return value;
    }

    public static int threeSumClosest03Demo(int[] nums, int target) {
        Arrays.sort(nums);
        int value = 0;
        int minValue = Integer.MAX_VALUE;
        for (int x = 0; x < nums.length - 2; x++) {
            int a1 = nums[x];
            int a2 = nums[x + 1];
            int a3 = nums[nums.length - 1];
            while (a2 < a3) {
                int sum = a1 + a2 + a3;
                int temp = Math.abs(target - sum);
                if (minValue > temp) {
                    minValue = temp;
                    value = sum;
                }
                if (sum > target) {
                    a3--;  // 错误原因，因为减小的应该是下标，而不是值
                } else {
                    a2++;
                }
            }
        }
        return value;
    }

    public static int threeSumClosest03(int[] nums, int target) {
        Arrays.sort(nums);
        int finValue = 0;
        int minValue = Integer.MAX_VALUE;
        String s = "";
        for (int i = 0; i < nums.length - 2; i++) {
            int firstOne = nums[i];
            // 变化的是下标
            int start = i + 1;
            int end = nums.length - 1;
            while (end > start) {
                int sum = firstOne + nums[start] + nums[end];
                if (minValue > Math.abs(target - sum)) {   // 并不能根据这个确定，下标是左移还是右移，因为这个值只是说更靠近target，可能是左移导致的更靠近，也可能是右移更靠近
                    minValue = Math.abs(target - sum);
                    finValue = sum;
                    s = "i:" + nums[i] + " start:" + nums[start] + " end:" + nums[end];
                }
                if (sum > target) {  // 所以只能通过和的值来确定
                    end--;
                } else if (sum < target) {
                    start++;
                } else {
                    return sum; // 相等必须列出来
                }
            }
        }
        System.out.println(s);
        return finValue;
    }

    public int threeSumClosest04(int[] nums, int target) {
        Arrays.sort(nums);
        int diff = nums[0] + nums[1] + nums[2] - target;
        for (int i = 0; i < nums.length - 2; i++) {
            int l = i + 1, r = nums.length - 1;
            while (l < r) {
                int curDiff = nums[i] + nums[l] + nums[r] - target;
                if (curDiff > 0) {
                    r--;
                } else if (curDiff < 0) {
                    l++;
                } else {
                    return target;
                }
                if (Math.abs(curDiff) < Math.abs(diff)) {
                    diff = curDiff;
                }
            }
        }
        return diff + target;
    }

}
